package com.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * TODO
 *
 * @author lefly
 * @version 1.0
 * @classname No39
 * @description 39. 组合总和
 * @date 2021/3/3 上午11:32
 */
public class No39 {
    public static void main(String[] args) {
        int[] candidates = {2,3,6,7};
        int target = 7;
        List<List<Integer>> res = combinationSum(candidates,target);
        for (int i = 0; i < res.size(); i++) {
            List<Integer> temp = res.get(i);
            for (int j = 0; j < temp.size(); j++) {
                System.out.print(temp.get(j));
                System.out.print(" ");
            }
            System.out.println();
        }
    }

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if(candidates == null || candidates.length == 0){
            return res;
        }
        // 排序
        Arrays.sort(candidates);
        List<Integer> list = new ArrayList<>();
        subCobinationSum(candidates,target,0,res,list);
        return res;
    }

    private static void subCobinationSum(int[] candidates, int target, int i, List<List<Integer>> res, List<Integer> list) {
        if(target < 0){
            return;
        }
        if(target == 0){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int start = i;start < candidates.length;start++){
            if(target < 0){
                break;
            }
            list.add(candidates[start]);
            subCobinationSum(candidates,target - candidates[start],start,res,list);
            list.remove(list.size() - 1);
        }
    }

}
